The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
11th International Conference on Relational Methods in Computer Science, RelMiCS 2009, and 6th International Conference on Applications of Kleene Algebra, AKA 2009, Doha, Qatar, November 1-5, 2009. Proceedings
While contemporary Game Theory has concentrated much on strategy, there is somewhat less attention paid to the role of knowledge and information transfer. There are exceptions to this rule of course, especially starting with the work of Aumann [2], and with contributions made by ourselves with coauthors Cogan, Krasucki and Pacuit [17,13]. But we have still only scratched the surface and there is still...
We present an overview of the potential of relation algebra and the software tool RelView, based on it, to compute solutions for problems from social choice. Using one leading example throughout the text, we subsequently show how the RelView tool may be used to compute and visualize minimal winning coalitions, swingers of a given coalition, vulnerable winning coalitions, central players, dominant...
Current Internet routing protocols exhibit several types of anomalies that can reduce network reliability. In order to design more robust protocols we need better formal models to capture the complexities of Internet routing. In this paper we develop an algebraic model that clarifies the distinction between routing tables and forwarding tables. We hope that this suggests new approaches to the design...
Kleene algebra is a great formalism for doing intraprocedural analysis and verification of programs, but it seems difficult to deal with interprocedural analysis where the power of context-free languages is often needed to represent both the program and the property. In the model checking framework, Alur and Madhusudan defined visibly pushdown automata, which accept a subclass of context-free languages...
We present an algebraic approach to separation logic. In particular, we give algebraic characterisations for all constructs of separation logic. The algebraic view does not only yield new insights on separation logic but also shortens proofs and enables the use of automated theorem provers for verifying properties at a more abstract level.
We axiomatise and study operations for relational domain and antidomain on semigroups and monoids. We relate this approach with previous axiomatisations for semirings, partial transformation semigroups and dynamic predicate logic.
Composition of the many-valued powerset partially ordered monad with the term monad provides extensions to non-classical relations and also new examples for Kleene algebras.
We provide a relation-algebraic characterization of liveness in Petri nets based on a relation-algebraic definition of both the structure and the state space of Petri nets. Such an approach, compared to the common ones that apply predicate logic and set theory, shifts the formalization to a more abstract level. As a main benefit, Petri net properties can be proved in a rigorous mathematical style...
In this paper, we introduce two notions of continuity for idempotent left semirings, which are called ∗-continuity and D-continuity. Also, for a ∗-continuous idempotent left semiring, we introduce a notion of ∗-ideals. Then, we show that the set of ∗-ideals of a ∗-continuous idempotent left semiring forms a D-continuous idempotent left semiring and the construction satisfies a universal property.
Equivalences, partitions and (bi)simulations are usually tackled using concrete relations. There are only few treatments by abstract relation algebra or category theory. We give an approach based on the theory of semirings and quantales. This allows applying the results directly to structures such as path and tree algebras which is not as straightforward in the other approaches mentioned. Also, the...
General correctness offers a finer semantics of programs than partial and total correctness. We give an algebraic account continuing and extending previous approaches. In particular, we propose axioms, correctness statements, a correctness calculus, specification constructs and a loop refinement rule. The Egli-Milner order is treated algebraically and we show how to obtain least fixpoints, used to...
A Concurrent Kleene Algebra offers two composition operators, one that stands for sequential execution and the other for concurrent execution [10]. In this paper we investigate the abstract background of this law in terms of independence relations on which a concrete trace model of the algebra is based. Moreover, we show the interdependence of the basic properties of such relations and two further...
It is well-known that Armstrong’s inference rules are sound and complete for functional dependencies of relational data bases and for implication in the theory of formal concepts by Wille and Ganter. In this paper the authors treat Armstrong’s inference rules and the implication as (binary) relations in an upper semi lattice in a Dedekind category, and give a relation algebraic proof of the completeness...
Association rules extraction from a binary relation as well as reasoning and information retrieval are generally based on the initial representation of the binary relation as an adjacency matrix. This presents some inconvenience in terms of space memory and knowledge organization. A coverage of a binary relation by a minimal number of non enlargeable rectangles generally reduces memory space consumption...
We define collagories essentially as “distributive allegories without zero morphisms”, and show that they are sufficient for accommodating the relation-algebraic approach to graph transformation. Collagories closely correspond to the adhesive categories important for the categorical DPO approach to graph transformation. but thanks to their relation-algebraic flavour provide a more accessible and more...
In this paper we want to extend the abstract approach to the size of a relation based on a cardinality function. Assuming suitable extra structure on the underlying distributive allegory we are going to define addition on cardinalities and investigate its basic properties.
Despite much progress in the design of programming languages, the vast majority of software being written and deployed nowadays remains written in languages where iteration is the main inductive construct, and the main source of algorithmic complexity. For the past four decades, the analysis of iterative constructs has been dominated, not undeservedly, by the concept of invariant assertions. In this...
While the popularity of statistical, probabilistic and exhaustive machine learning techniques still increases, relational and logic approaches are still a niche market in research. While the former approaches focus on predictive accuracy, the latter ones prove to be indispensable in knowledge discovery. In this paper we present a relational description of machine learning problems. We demonstrate...
We refine and extend the known results that the set of ordinary binary relations forms a Kleene algebra, the set of up-closed multirelations forms a lazy Kleene algebra, the set of up-closed finite multirelations forms a monodic tree Kleene algebra, and the set of total up-closed finite multirelations forms a probabilistic Kleene algebra. For the refinement, we introduce a notion of type of multirelations...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.